package leetcode_800;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *AllPathsFromSourceToTarget_797 一个无循环有向图 问A-B的所有路径
 *describe:用深搜回溯 AC 69%
 *2018年10月23日 上午11:14:04
 */
public class AllPathsFromSourceToTarget_797 {
	List<List<Integer>> res;
	int[][]graph;
	public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
		this.res=new ArrayList<List<Integer>>();
		this.graph=graph;
		List<Integer> path=new ArrayList<Integer>();
		help(path,0);
		return this.res;
    }
	
	public void help(List<Integer> path,int now) {
		path.add(now);
		if(now==graph.length-1) {//到达目的
			List<Integer> temp=new ArrayList<Integer>(path);
			this.res.add(temp);
		}
		else {
			for(int i=0;i<graph[now].length;++i) {
				help(path,graph[now][i]);
			}
		}
		path.remove(path.size()-1);//回溯
	}
}
